berechenbare Funktion

I

berechenbare Funktion,

 

Informatik, mathematische Logik: eine Funktion f : M → N, für die es einen Algorithmus gibt, der für jeden Eingabewert m ∈ M, für den die Funktion definiert ist, nach endlich vielen Schritten anhält und das Ergebnis f (m) liefert; in allen Fällen, in denen f (m) nicht definiert ist, bricht der Algorithmus nicht ab. Beispielsweise ist die Funktion, die zu zwei natürlichen Zahlen ihren größten gemeinsamen Teiler liefert, berechenbar. - Aufgrund der churchschen Hypothese ist die Klasse der berechenbaren Funktionen gleich der Klasse der Funktionen, die durch Turing-Maschinen berechnet werden. Da diese selbst nur ein formales Modell für einen Computer (mit beliebig viel Speicher) und sein Programm darstellen, kann man jede berechenbare Funktion als Programm formulieren und auf einer Rechenanlage ausführen lassen.

II

berechenbare Funktion,

 

eine Funktion, für die es einen Algorithmus gibt, der für jeden erlaubten Eingabewert nach endlich vielen Schritten anhält und ein eindeutiges Ergebnis liefert; in allen Fällen, in denen eine Eingabe nicht im Definitionsbereich der Funktion liegt, bricht der Algorithmus nicht ab. Beispielsweise ist die Funktion, die zu zwei natürlichen Zahlen ihren größten gemeinsamen Teiler liefert, berechenbar. Gilt die churchsche These (Turing-Maschine), sind die berechenbaren Funktionen gerade die Funktionen, die durch Turing-Maschinen berechnet werden. Da diese selbst nur ein formales Modell für einen Computer (mit beliebig großem Speicher) und sein Programm darstellen, kann man jede berechenbare Funktion als Programm formulieren und auf einer Rechenanlage ausführen lassen.